using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

namespace DataStructure
{
    public static class SearchAlgorithms 
    {
        //[1]顺序查找
        //时间复杂度O(n) , 空间复杂度O(1)
        public static int OrderSearch(int[] arr, int target)
        {  
            for (int i = 0; i < arr.Length; i++)
                if (arr[i] == target)
                    return i;
                    
            return -1;
        }
        
        //[2]二分查找=>只能用于有序数组
        //时间复杂度O(log n) , 空间复杂度O(1)
        public static int BinarySearch(int[] arr, int target)
        {
            int l = 0;
            int r = arr.Length-1;
            
            while(l <= r)
            {
                //避免整数溢出(l + r可能非常大，从而超出整数范围)
                int mid = l + (r - l)/2;
                
                if(target < arr[mid])
                    r = mid-1;
                else if(target > arr[mid])
                    l = mid+1;
                else
                    return mid;
            }
            return -1;
        }
        
        //[3]插值查找=>只能用于有序数组
        //时间复杂度O(log log n) , 空间复杂度O(1)
        public static int InsertionSearch(int[] arr, int target)
        {
            // 检查数组是否为空
            if (arr == null || arr.Length == 0)
                return -1;

            int l = 0;
            int r = arr.Length - 1;

            while (l <= r && target >= arr[l] && target <= arr[r])
            {
                // 防止除数为零情况
                if (arr[l] == arr[r])
                {
                    if (arr[l] == target)
                        return l; // 或者返回 r，两者相等
                    return -1;
                }

                // 计算插值位置 pos
                int pos = l + (target - arr[l]) * (r - l) / (arr[r] - arr[l]);

                // 检查 pos 是否在有效范围内
                if (pos < l || pos > r)
                    break;

                if (arr[pos] == target)
                    return pos;

                if (target < arr[pos])
                    r = pos - 1;
                else
                    l = pos + 1;
            }
            return -1;
        }

    }
}